#include <stdio.h>
#include <stdlib.h>
#include "stack.h"
#include "queue.h"

typedef int DataType;
enum bool {
        false, true
};
typedef enum bool Bool;

struct BinTreeNode {
        DataType val;
        struct BinTreeNode *left;
        struct BinTreeNode *right;
};
typedef struct BinTreeNode *PBinTreeNode;
typedef struct BinTreeNode *BinTree;

void PreOrder(BinTree t)
{
        if (!t) {
                return ;
        }
        printf("%d ", t->val);
        PreOrder(t->left);
        PreOrder(t->right);
}

void InOrder(BinTree t)
{
        if (!t) {
                return ;
        }
        InOrder(t->left);
        printf("%d ", t->val);
        InOrder(t->right);
}

void PostOrder(BinTree t)
{
        if (!t) {
                return ;
        }
        PostOrder(t->left);
        PostOrder(t->right);
        printf("%d ", t->val);
}

void InOrder_2(BinTree t)
{
        BinTree bt;
        Stack s = CreateStack();
        bt = t;
        while (bt || !isEmpty(s)) {
                while (bt) {
                        Push(s, bt);
                        bt = bt->left;
                }
                bt = Pop(s);
                printf("%d", bt->val);
                bt = bt->right;
        }
}

void LevelOrder(BinTree t)
{
        Queue q;
        BinTree bt;
        if (!t) return ;
        q = CreateQueue();
        AddQ(q, t);
        while (!IsEmpty(q)) {
                bt = DeleteQ(q);
                printf("%d ", bt->val);
                if (bt->left) AddQ(q, bt->left);
                if (bt->right) AddQ(q, bt->right);
        }
}

// 统计叶子结点的个数.
void leaf(BinTree BT)
{
        if (!BT) return ;
        int n = 0;
        // 若该结点左右子树都不存在就为叶子结点.
        if (!BT->left && !BT->right) {
                n++;
        }
        leaf(BT->left);
        leaf(BT->right);
}

// 在二叉树bt中查找元素x.
BinTree Search(BinTree bt, DataType x)
{
        if (!bt) return ;
        BinTree p;
        if (bt->val == x) return bt;
        else if (bt->left) {
                p = Search(bt->left, x);
                if (p) return p;
        }
        else if (bt->right) {
                p = Search(bt->right, x);
                if (p) return p;
        }
        return NULL;
}
